package BinarySearch._436_FindRightInterval;

import java.util.*;

public class _436_FindRightInterval {
    public int[] findRightInterval(Interval[] intervals) {
        Map<Integer, Integer> maps = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            maps.put(intervals[i].start, i);
        }
        Arrays.sort(intervals,(a,b)->a.start-b.start);
        int[] res = new int[intervals.length];
        Arrays.fill(res, -1);
        for (int i = 0; i < res.length; i++) {
            int start = i + 1, end = res.length - 1;
            while (start < end) {
                int middle = (start + end) / 2;
                if (intervals[i].end <= intervals[middle].start) {
                    end = middle;
                } else {
                    start = middle + 1;
                }
            }
            if (start < res.length && intervals[i].end <= intervals[start].start) {
                res[maps.get(intervals[i].start)] = maps.get(intervals[start].start);
            }
        }
        return res;
    }
}
